#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1e4,p=998244353;
static int f[N+1];
inline int add(int x,int y){
  int s=x+y; if(s>=p)s-=p; return s;
}
inline int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=1ll*r*a%p;
    a=1ll*a*a%p,b>>=1;
  }
  return r;
}
inline int com(int n,int m){
  return 1ll*f[n]*qpow(1ll*f[m]*f[n-m]%p,p-2)%p;
}
int main(){
  freopen("oi.in","r",stdin);
  freopen("oi.out","w",stdout);
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  for(int i=f[0]=1;i<=N;i++)
    f[i]=1ll*f[i-1]*i%p;
  int id,t; cin>>id>>t;
  while(t--){
    int n,m; cin>>n>>m;
    vector<pii> E(m);
    vector<vector<int> > g(n);
    for(int i=0;i<m;i++){
      int u,v; cin>>u>>v;
      E[i]=make_pair(--u,--v);
      g[u].emplace_back(v);
      g[v].emplace_back(u);
    }
    if(n<=5){
      vector<pii> e;
      for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
          e.emplace_back(i,j);
      int w=-1e9,c=0;
      for(int S=0;S<1<<e.size();S++)
        if(__builtin_popcount(S)==m-1){
          vector<vector<int> > f(n,vector<int>(n,1e9));
          for(int i=0;i<n;i++)f[i][i]=0;
          for(int i=0;i<e.size();i++)
            if(S>>i&1){
              int u,v; tie(u,v)=e[i];
              f[u][v]=f[v][u]=1;
            }
          for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
              for(int k=0;k<n;k++)
                f[j][k]=min(f[j][k],f[j][i]+f[i][k]);
          int w0=0;
          for(auto i:E){
            if(f[i.first][i.second]==1e9){
              w0=-1e9; break;
            }
            else w0-=f[i.first][i.second];
          }
          if(w0>w)w=w0,c=1;
          else if(w0==w)c++;
        }
      cout<<w<<' '<<c<<'\n'; continue;
    }
    if(3<=id&&id<=4){
      n--,cout<<-(n<<1)<<' '<<1ll*com(n*3,n)*qpow(n<<1|1,p-2)%p<<'\n'; continue;
    }
    vector<int> d(n,-1);
    int w=-1e9,c=0;
    function<void(int,int)> dfs=[&](int u,int f){
      for(int i:g[u])
        if(i!=f){
          if(d[i]<0)d[i]=d[u]+1,dfs(i,u);
          else{
            int x=-abs(d[u]-d[i]);
            if(x>w)w=x,c=2;
            else if(x==w)c++;
          }
        }
    };
    for(int i=0;i<n;i++)
      if(d[i]<0)d[i]=0,dfs(i,-1);
    c>>=1,cout<<w-m+1<<' '<<1ll*c*com(abs(w)*3,abs(w))%p*qpow(abs(w)<<1|1,p-2)%p<<'\n';
  }
  return 0;
}